# Day01  01理想火车站定位  2024/11/06
def solution(n, m, citizens, locations):
    # 初始化最小总距离和最佳火车站位置
    min_total_distance = float('inf')
    best_location = [-1, -1]

    # 遍历每个备选火车站位置
    for location in locations:
        # 计算当前备选位置到所有市民位置的曼哈顿总距离
        total_distance = 0
        for citizen in citizens:
            total_distance += abs(location[0] - citizen[0]) + abs(location[1] - citizen[1])

        # 如果当前总距离比已知最小总距离更小，更新最佳位置
        if total_distance < min_total_distance:
            min_total_distance = total_distance
            best_location = location

    return best_location


if __name__ == "__main__":
    #  You can add more test cases here
    citizens1 = [[-1, -1], [-1, 1], [1, -1], [1, 1]]
    locations1 = [[3, 2], [1, 0], [0, 0]]
    print(solution(4, 3, citizens1, locations1) == [1, 0])


# Day02  02小E的射击训练  2024/11/10
def solution(x: int, y: int) -> int:
    # 计算射击点到靶心的距离平方
    distance_squared = x * x + y * y

    # 逐层判断射击点所在的环，距离平方 <= i^2 则属于该环
    for i in range(1, 11):
        if distance_squared <= i * i:
            return 11 - i

    # 若距离超出所有环，则返回0分
    return 0


if __name__ == '__main__':
    print(solution(1, 0) == 10)  # 靶心内得10分
    print(solution(1, 1) == 9)  # 在第2环得9分
    print(solution(0, 5) == 6)  # 在第5环得6分
    print(solution(3, 4) == 6)  # 在第5环得6分


# Day03  03a替换函数  2024/11/11
def solution(s: str) -> str:
    # 将字符串中的所有小写字母 'a' 替换为 '%100'
    return s.replace("a", "%100")


if __name__ == '__main__':
    # 测试用例
    print(solution(s="abcdwa") == '%100bcdw%100')
    print(solution(s="banana") == 'b%100n%100n%100')
    print(solution(s="apple") == '%100pple')


# Day03  04完美偶数计数  2024/11/11
def solution(n: int, l: int, r: int, a: list) -> int:
    # 初始化计数器
    count = 0
    # 遍历数组中的每个元素
    for num in a:
        # 检查是否为偶数且在区间 [l, r] 范围内
        if num % 2 == 0 and l <= num <= r:
            count += 1
    return count


if __name__ == '__main__':
    # 测试用例
    print(solution(5, 3, 8, [1, 2, 6, 8, 7]) == 2)
    print(solution(4, 10, 20, [12, 15, 18, 9]) == 2)
    print(solution(3, 1, 10, [2, 4, 6]) == 3)


# Day03  05小S的倒排索引 2024/11/11
def solution(a, b):
    # 将列表 a 和 b 转换为集合
    set_a = set(a)
    set_b = set(b)
    # 找出两个集合的交集并按降序排序
    result = sorted(set_a & set_b, reverse=True)
    return result


if __name__ == '__main__':
    # 测试用例
    print(solution([1, 2, 3, 7], [2, 5, 7]) == [7, 2])
    print(solution([1, 4, 8, 10], [2, 4, 8, 10]) == [10, 8, 4])
    print(solution([3, 5, 9], [1, 4, 6]) == [])
    print(solution([1, 2, 3], [1, 2, 3]) == [3, 2, 1])


# Day04  06组成字符串ku的最大次数   2024/11/12
def solution(s: str) -> int:
    # 将字符串转换为小写
    s = s.lower()

    # 统计 'k' 和 'u' 的出现次数
    count_k = s.count('k')
    count_u = s.count('u')

    # 返回 'k' 和 'u' 数量的最小值
    return min(count_k, count_u)


# 测试示例
if __name__ == '__main__':
    print(solution("AUBTMKAxfuu") == 1)  # 输出: 1
    print(solution("KKuuUuUuKKKKkkkkKK") == 6)  # 输出: 6
    print(solution("abcdefgh") == 0)  # 输出: 0


# Day05   07找出整型数组中占比超过一半的数字   2024/11/13
def solution(array):
    # 摩尔投票法：找到候选的多数元素
    candidate, count = None, 0
    for num in array:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)

    # 验证候选元素是否超过一半
    if array.count(candidate) > len(array) // 2:
        return candidate
    return None


if __name__ == "__main__":
    # 测试用例
    print(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)
    print(solution([5, 5, 5, 1, 2, 5, 5]) == 5)
    print(solution([9, 9, 9, 8, 8, 9, 8, 9, 9]) == 9)


# Day05   08不同整数的计数问题   2024/11/13
def solution(word: str) -> int:
    import re
    # 使用正则表达式查找所有连续的数字子串
    numbers = re.findall(r'\d+', word)
    # 去掉每个数字的前导零，并将其转换为整数，最后使用集合去重
    unique_numbers = {int(num) for num in numbers}
    # 返回不同整数的数量
    return len(unique_numbers)


if __name__ == '__main__':
    # 测试用例
    print(solution("a123bc34d8ef34") == 3)  # 输出: 3
    print(solution("t1234c23456") == 2)  # 输出: 2
    print(solution("a1b01c001d4") == 2)  # 输出: 2


# Day06   09最大乘积区间问题   2024/11/14
def solution(n, data):
    if n == 1:
        return [1, 1]
    max_product = float('-inf')
    start = 1
    end = 1
    for i in range(n):
        product = 1
        for j in range(i, n):
            product *= data[j]
            if product > max_product:
                max_product = product
                start = i + 1
                end = j + 1
            elif product == max_product and (i + 1 < start or (i + 1 == start and j + 1 < end)):
                start = i + 1
                end = j + 1
    return [start, end]
    return [-1, -1]


if __name__ == "__main__":
    # Add your test cases here
    print(solution(5, [1, 2, 4, 0, 8]) == [1, 3])
    print(solution(7, [1, 2, 4, 8, 0, 256, 0]) == [6, 6])


# Day06   10数字增殖问题   2024/11/14
def solution(n, k, p):
    # 用于缓存每个数字在不同增殖次数后的序列长度，避免重复计算
    length_cache = {}

    # 计算从数字x开始，经过k次增殖后形成的序列长度
    def get_sequence_length(x, k):
        if (x, k) in length_cache:
            return length_cache[(x, k)]
        if k == 0:  # 当增殖次数为0时，序列长度就是1
            return 1
        # 递归计算本次增殖后的序列长度
        length = sum(get_sequence_length(i, k - 1) for i in range(1, x + 1))
        length_cache[(x, k)] = length
        return length

    # 找到第p个位置的值
    def find_value(x, k, p):
        if k == 0:  # 当增殖次数为0时，直接返回数字本身
            return x
        # 遍历每个子区间，找到p所在的区间
        for i in range(1, x + 1):
            sub_length = get_sequence_length(i, k - 1)  # 计算子区间的长度
            if p <= sub_length:
                # 如果p在这个子区间内，递归进入这个子区间
                return find_value(i, k - 1, p)
            p -= sub_length  # 如果不在，更新p的位置
        return -1  # 超出范围返回-1

    # 初始调用
    result = find_value(n, k, p)
    return result


# 测试样例
if __name__ == "__main__":
    print(solution(4, 3, 19) == 3)  # 输出: True


# Day07   11贪心猫的鱼干大分配   2024/11/15
def solution(n, cats_levels):
    # 初始化每只猫的鱼干数，初始时每只猫至少得到 1 斤
    fish = [1] * n

    # 从左到右遍历，满足左边低等级的猫分配更少的鱼干
    for i in range(1, n):
        if cats_levels[i] > cats_levels[i - 1]:
            fish[i] = fish[i - 1] + 1

    # 从右到左遍历，满足右边低等级的猫分配更少的鱼干
    for i in range(n - 2, -1, -1):
        if cats_levels[i] > cats_levels[i + 1]:
            fish[i] = max(fish[i], fish[i + 1] + 1)

    # 计算总共的鱼干数
    return sum(fish)


if __name__ == "__main__":
    # 测试样例
    cats_levels1 = [1, 2, 2]
    cats_levels2 = [6, 5, 4, 3, 2, 16]
    cats_levels3 = [1, 2, 2, 3, 3, 20, 1, 2, 3, 3, 2, 1, 5, 6, 6, 5, 5, 7, 7, 4]
    print(solution(3, cats_levels1) == 4)  # 输出: True
    print(solution(6, cats_levels2) == 17)  # 输出: True
    print(solution(20, cats_levels3) == 35)  # 输出: True


# Day07   12游戏排名第三大的分数   2024/11/15
def solution(n: int, nums: list) -> int:
    # 使用集合去重得到不同的分数
    unique_scores = list(set(nums))

    # 将不同的分数按降序排列
    unique_scores.sort(reverse=True)

    # 如果有三个或以上不同的分数，返回第三大的分数
    if len(unique_scores) >= 3:
        return unique_scores[2]
    else:
        # 如果不足三个不同的分数，返回最大的分数
        return unique_scores[0]


if __name__ == '__main__':
    print(solution(3, [3, 2, 1]) == 1)  # True
    print(solution(2, [1, 2]) == 2)  # True
    print(solution(4, [2, 2, 3, 1]) == 1)  # True

# Day07   13最小替换字串长度  2024/11/15
from collections import Counter


def solution(input_str):
    n = len(input_str)
    target_freq = n // 4  # 每个字符的目标频次

    # 统计字符串中各字符的出现次数
    count = Counter(input_str)

    # 如果已经平衡，直接返回0
    if count['A'] == count['S'] == count['D'] == count['F'] == target_freq:
        return 0

    # 滑动窗口的左右指针
    left = 0
    min_len = n  # 初始最小长度为整个字符串的长度

    # 遍历右指针
    for right in range(n):
        count[input_str[right]] -= 1  # 扩展窗口，更新右指针位置的字符

        # 进行窗口收缩
        while left <= right and all(count[c] <= target_freq for c in 'ASDF'):
            # 如果窗口内可以调整，计算窗口大小并更新最小长度
            min_len = min(min_len, right - left + 1)
            # 缩小窗口，移动左指针
            count[input_str[left]] += 1
            left += 1

    return min_len


# 测试用例
if __name__ == "__main__":
    print(solution("ADDF") == 1)  # 输出: 1
    print(solution("ASAFASAFADDD") == 3)  # 输出: 3
    print(solution("SSDDFFFFAAAS") == 1)  # 输出: 1
    print(solution("AAAASSSSDDDDFFFF") == 0)  # 输出: 0
    print(solution("AAAADDDDAAAASSSS") == 4)  # 输出: 4

# Day07   14查找热点数据问题  2024/11/15
import heapq
from collections import Counter


def solution(nums, k):
    # 统计每个元素的频率
    freq_map = Counter(nums)

    # 使用最小堆来保存频率最高的 k 个元素
    heap = []

    for num, freq in freq_map.items():
        # 把频率和元素以元组的形式插入堆中
        heapq.heappush(heap, (freq, num))
        # 保持堆的大小为 k
        if len(heap) > k:
            heapq.heappop(heap)

    # 提取堆中的元素，按升序排序
    top_k = [num for freq, num in heap]
    top_k.sort()

    # 返回按升序排列的数字，拼接成字符串
    return ",".join(map(str, top_k))


# 测试用例
if __name__ == "__main__":
    # You can add more test cases here
    print(solution([1, 1, 1, 2, 2, 3], 2))  # 输出: "1,2"
    print(solution([1], 1))  # 输出: "1"
    print(solution([4, 4, 4, 2, 2, 2, 3, 3, 1], 2))  # 输出: "2,4"


# Day07   15古生物DNA序列血缘分析  2024/11/15
def solution(dna1, dna2):
    m, n = len(dna1), len(dna2)

    # 创建一个 (m+1) x (n+1) 的二维数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化边界条件
    for i in range(m + 1):
        dp[i][0] = i  # dna1 到空字符串需要删除 i 个字符

    for j in range(n + 1):
        dp[0][j] = j  # 空字符串到 dna2 需要插入 j 个字符

    # 填充 dp 数组
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if dna1[i - 1] == dna2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # 字符相同，不需要操作
            else:
                dp[i][j] = min(dp[i - 1][j] + 1,  # 删除
                               dp[i][j - 1] + 1,  # 插入
                               dp[i - 1][j - 1] + 1)  # 替换

    return dp[m][n]


# 测试样例
if __name__ == "__main__":
    # 你可以在这里添加更多的测试用例
    print(solution("AGT", "AGCT") == 1)  # 输出: 1
    print(solution("", "ACGT") == 4)  # 输出: 4
    print(solution("GCTAGCAT", "ACGT") == 5)  # 输出: 5


# Day08   16RGB色值转换为整数值  2024/11/16
def solution(rgb):
    """
    将RGB字符串转换为十六进制整数值。

    参数:
    - rgb: RGB字符串 (str), 格式为 "rgb(R, G, B)"

    返回:
    - 十六进制整数值 (int)
    """
    # 去除字符串中的非数字和逗号，提取RGB值
    rgb = rgb.replace("rgb(", "").replace(")", "")
    r, g, b = map(int, rgb.split(", "))  # 提取 R、G、B 值

    # 计算十六进制整数值
    return (r << 16) + (g << 8) + b


if __name__ == "__main__":
    # 测试用例
    print(solution("rgb(192, 192, 192)") == 12632256)  # True
    print(solution("rgb(100, 0, 252)") == 6553852)  # True
    print(solution("rgb(33, 44, 55)") == 2174007)  # True

# Day08   17分组飞行棋棋子  2024/11/16
from collections import Counter


def solution(nums):
    """
    判断是否可以将棋子分为 M 组，每组 5 个且序号相同。

    参数:
    - nums: 棋子序号列表 (List[int])

    返回:
    - "True" 或 "False" (str)
    """
    # 统计每个序号的频率
    freq = Counter(nums)

    # 检查棋子总数是否为 5 的倍数
    if len(nums) % 5 != 0:
        return "False"

    # 检查每个序号的频率是否为 5 的倍数
    for count in freq.values():
        if count % 5 != 0:
            return "False"

    return "True"


if __name__ == "__main__":
    # 测试用例
    print(solution([1, 2, 3, 4, 5]) == "False")  # 样例 1
    print(solution([1, 1, 1, 1, 2, 1, 2, 2, 2, 2]) == "True")  # 样例 2
    print(solution([5, 5, 5, 5, 5, 5, 5, 5, 5, 5]) == "True")  # 样例 3
    print(solution([7, 7, 7, 8, 8, 8, 8, 8, 7, 7]) == "True")  # 样例 4
    print(solution([9, 9, 9, 9, 9, 9, 9]) == "False")  # 样例 5


# Day08   18兔群繁殖之谜  2024/11/16
def solution(A):
    if A == 1:
        return 1
    a, b = 1, 1
    for i in range(A - 1):
        a, b = b, a + b
    return b


if __name__ == "__main__":
    # 测试用例
    print(solution(5) == 8)  # 第5个月末兔子的数量应该是 8
    print(solution(1) == 1)  # 第1个月末兔子的数量应该是 1
    print(solution(15) == 987)  # 第15个月末兔子的数量应该是 987
    print(solution(50) == 20365011074)  # 第50个月末兔子的数量应该是 20365011074


# Day09   19机器人能量冒险  2024/11/17
def solution(n, array):
    # 最大能到达的位置
    max_reach = 0

    for i in range(n):
        # 如果当前位置超过了最大可到达位置，无法前进
        if i > max_reach:
            return "FALSE"

        # 更新最大可到达位置
        max_reach = max(max_reach, i + array[i])

        # 如果最大可到达位置已经超过或到达最后一个位置，返回 TRUE
        if max_reach >= n - 1:
            return "TRUE"

    return "FALSE"


if __name__ == "__main__":
    # 测试用例
    print(solution(5, [2, 3, 1, 1, 4]) == "TRUE")  # 样例1
    print(solution(5, [3, 2, 1, 0, 4]) == "FALSE")  # 样例2
    print(solution(6, [1, 2, 3, 4, 0, 0]) == "TRUE")  # 样例3


# Day09   20游戏队友搜索  2024/11/17
def solution(id, num, array):
    from collections import defaultdict

    # 构建游戏到玩家的映射和玩家到游戏的映射
    game_to_players = defaultdict(set)
    player_to_games = defaultdict(set)

    for player, game in array:
        game_to_players[game].add(player)
        player_to_games[player].add(game)

    # 目标玩家的游戏记录
    target_games = player_to_games[id]
    potential_teammates = defaultdict(int)

    # 统计与目标玩家共同比赛次数的玩家
    for game in target_games:
        for teammate in game_to_players[game]:
            if teammate != id:
                potential_teammates[teammate] += 1

    # 过滤队友：共同比赛次数 >= 2
    result = [player for player, count in potential_teammates.items() if count >= 2]

    # 按升序排序返回
    return sorted(result)


if __name__ == "__main__":
    # 测试用例
    print(
        solution(
            1,
            10,
            [
                [1, 1],
                [1, 2],
                [1, 3],
                [2, 1],
                [2, 4],
                [3, 2],
                [4, 1],
                [4, 2],
                [5, 2],
                [5, 3],
            ],
        )
        == [4, 5]
    )
    print(solution(2, 6, [[2, 1], [2, 3], [1, 1], [1, 2], [3, 1], [4, 3]]) == [])
    print(
        solution(
            3,
            8,
            [[3, 1], [3, 2], [3, 3], [4, 1], [5, 2], [6, 3], [7, 1], [7, 2]]
        )
        == [7]
    )


# Day09   21最优硬币组合问题  2024/11/17
def solution(coins, amount):
    # 初始化动态规划数组
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 凑出金额 0 不需要硬币

    # backtrack 数组记录选择的硬币
    backtrack = [-1] * (amount + 1)

    # 动态规划求解最少硬币数
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                backtrack[i] = coin

    # 如果无法凑出目标金额
    if dp[amount] == float('inf'):
        return []

    # 根据 backtrack 数组还原硬币组合
    result = []
    while amount > 0:
        result.append(backtrack[amount])
        amount -= backtrack[amount]

    # 倒序输出结果
    return result[::-1]


if __name__ == "__main__":
    # 测试用例
    print(solution([1, 2, 5], 18))  # 输出 [1, 2, 5, 5, 5]
    print(solution([1, 3, 4], 6))  # 输出 [3, 3]
    print(solution([5], 10))  # 输出 [5, 5]
    print(solution([2], 3))  # 输出 [] 无法凑出


# Day09   22字符串“chhc”字串权值求和  2024/11/17
def solution(s: str) -> int:
    n = len(s)
    target = "chhc"
    target_len = len(target)
    total_weight = 0

    for i in range(n - target_len + 1):
        # 检查长度为 4 的子串是否是 "chhc"
        if s[i:i + target_len] == target:
            # 计算贡献
            left_contrib = i + 1  # 左侧子串选择起点的方式
            right_contrib = n - (i + target_len) + 1  # 右侧子串选择终点的方式
            total_weight += left_contrib * right_contrib

    return total_weight


if __name__ == '__main__':
    print(solution("chhchhc") == 8)  # 输出 8
    print(solution("chhcchhcchhc") == 43)  # 输出 43
    print(solution("hhhh") == 0)  # 输出 0


# Day09   23小A的移动点  2024/11/17
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1


def solution(n: int, points: list) -> int:
    x_map = {}
    y_map = {}
    uf = UnionFind(n)

    for i, (x, y) in enumerate(points):
        if x in x_map:
            uf.union(i, x_map[x])
        x_map[x] = i

        if y in y_map:
            uf.union(i, y_map[y])
        y_map[y] = i

    # 统计连通分量
    unique_roots = len(set(uf.find(i) for i in range(n)))
    return unique_roots - 1  # 至少需要添加的点数


if __name__ == '__main__':
    # 测试样例
    print(solution(2, [[1, 1], [2, 2]]) == 1)  # 输出 1
    print(solution(3, [[1, 2], [2, 3], [4, 1]]) == 2)  # 输出 2
    print(solution(4, [[3, 4], [5, 6], [3, 6], [5, 4]]) == 0)  # 输出 0


# Day010   24套碗游戏的取碗顺序问题   2024/11/18
def solution(M: int, a: list) -> int:
    # 栈用于模拟木棍上的碗
    stack = []
    # 当前从木棍上可以压入栈的碗编号，从 1 开始递增到 M
    current = 1

    # 遍历给定的取碗顺序
    for num in a:
        # 如果栈为空或栈顶与当前需要的编号不匹配，则将碗压入栈
        while current <= M and (not stack or stack[-1] != num):
            stack.append(current)
            current += 1

        # 如果栈顶匹配当前需要的碗编号，弹出栈顶
        if stack[-1] == num:
            stack.pop()
        else:
            # 如果栈顶与当前需要的编号不匹配，说明顺序不合法
            return 0

    # 如果顺序合法，返回 1
    return 1


if __name__ == '__main__':
    print(solution(2, [1, 2]) == 1)  # 输出 True
    print(solution(3, [3, 1, 2]) == 0)  # 输出 True
    print(solution(4, [1, 3, 2, 4]) == 1)  # 输出 True


# Day010   25寻找独一无二的糖葫芦串   2024/11/18
def solution(n: int, m: int, strings: list) -> int:
    # 字典用于记录每种糖葫芦及其翻转的出现次数
    candy_map = {}
    for s in strings:
        # 将字符串和其翻转按字典序排序，统一表示为最小字符串
        canonical = min(s, s[::-1])
        candy_map[canonical] = candy_map.get(canonical, 0) + 1

    # 遍历糖葫芦列表，找到甜度最大的独一无二的糖葫芦
    max_sweetness = 0
    for s in strings:
        # 计算当前糖葫芦甜度
        sweetness = sum(ord(char) - ord('a') for char in s)
        # 检查独一无二性
        if candy_map[min(s, s[::-1])] == 1:
            max_sweetness = max(max_sweetness, sweetness)

    # 如果没有独一无二的糖葫芦，返回 0
    return max_sweetness


if __name__ == "__main__":
    print(solution(3, 3, ["ccz", "cba", "zcc"]) == 3)  # 输出 True
    print(solution(2, 3, ["abc", "cba"]) == 0)  # 输出 True
    print(solution(5, 2, ["aa", "bb", "ab", "ba", "cc"]) == 4)  # 输出 True


# Day010   26五子棋的获胜策略   2024/11/18
def solution(x, y):
    # 检查给定位置是否能形成五子连线
    def can_form_five(x, y, board):
        # 定义方向：横向、纵向、两个斜向
        directions = [(0, 1), (1, 0), (1, 1), (1, -1)]
        for dx, dy in directions:
            count = 1  # 当前点的棋子计数
            # 正向检查
            for step in range(1, 5):
                nx, ny = x + step * dx, y + step * dy
                if 0 <= nx < len(board) and 0 <= ny < len(board) and board[nx][ny] == 1:
                    count += 1
                else:
                    break
            # 反向检查
            for step in range(1, 5):
                nx, ny = x - step * dx, y - step * dy
                if 0 <= nx < len(board) and 0 <= ny < len(board) and board[nx][ny] == 1:
                    count += 1
                else:
                    break
            # 如果达成五子连线
            if count >= 5:
                return True
        return False

    # 结果列表
    result = []
    for i in range(x):
        for j in range(x):
            if y[i][j] == 0:  # 空位
                y[i][j] = 1  # 暂时放置棋子
                if can_form_five(i, j, y):
                    result.append([i + 1, j + 1])  # 记录1-based索引
                y[i][j] = 0  # 还原棋盘状态

    return result


if __name__ == "__main__":
    # 测试用例
    array = [
        [0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 1, 0],
        [0, 0, 0, 0, 0, 0],
    ]

    print(solution(6, array) == [[1, 1], [6, 6]])


# Day10   27小M的多任务下载器挑战   2024/11/18
def solution(n, array):
    # 记录任务的时间变化点
    timeline = []
    for x, y in array:
        start = x
        end = x + y - 1
        timeline.append((start, 1))  # 任务开始
        timeline.append((end + 1, -1))  # 任务结束后

    # 排序时间点，按时间升序，若时间相同按任务增减值排序
    timeline.sort()

    max_concurrent = 0  # 最大并发数
    current_concurrent = 0  # 当前并发数

    # 遍历时间线
    for _, delta in timeline:
        current_concurrent += delta
        max_concurrent = max(max_concurrent, current_concurrent)

    return max_concurrent


if __name__ == "__main__":
    # 测试用例
    print(solution(2, [[1, 2], [2, 3]]) == 2)  # 输出: True
    print(solution(4, [[1, 2], [2, 3], [3, 5], [4, 3]]) == 3)  # 输出: True


# Day10   28版本号比较   2024/11/18
def solution(version1, version2):
    # 将版本号通过'.'分割成一个个数字
    v1_parts = version1.split('.')
    v2_parts = version2.split('.')

    # 确保两个版本号的长度相同，不足的部分补充为 '0'
    length = max(len(v1_parts), len(v2_parts))

    for i in range(length):
        # 获取当前修订号，如果不存在则当作 '0'
        v1 = int(v1_parts[i]) if i < len(v1_parts) else 0
        v2 = int(v2_parts[i]) if i < len(v2_parts) else 0

        # 比较修订号
        if v1 > v2:
            return 1
        elif v1 < v2:
            return -1

    # 所有修订号相等，返回 0
    return 0


if __name__ == "__main__":
    # Add your test cases here
    print(solution("0.1", "1.1") == -1)
    print(solution("1.0.1", "1") == 1)
    print(solution("7.5.2.4", "7.5.3") == -1)
    print(solution("1.0", "1.0.0") == 0)


# Day11   29字符串字符类型排序问题   2024/11/19
def solution(inp):
    # 拆分输入字符串，提取数字和字母，并记录它们的原始索引
    numbers = []
    letters = []
    positions = []  # 用于记录非问号字符的位置和类型
    for i, char in enumerate(inp):
        if char.isdigit():
            numbers.append(char)
            positions.append((i, 'number'))
        elif char.isalpha():
            letters.append(char)
            positions.append((i, 'letter'))

    # 分别对数字和字母排序
    numbers.sort(reverse=True)  # 数字按从大到小排序
    letters.sort()  # 字母按字典序排序

    # 构造结果字符串
    result = list(inp)  # 将字符串转为列表便于按索引替换
    num_index = 0
    letter_index = 0

    for pos, char_type in positions:
        if char_type == 'number':
            result[pos] = numbers[num_index]
            num_index += 1
        elif char_type == 'letter':
            result[pos] = letters[letter_index]
            letter_index += 1

    return ''.join(result)


if __name__ == "__main__":
    # 测试用例
    print(solution("12A?zc") == "21A?cz")  # 输出 True
    print(solution("1Ad?z?t24") == "4Ad?t?z21")  # 输出 True
    print(solution("???123??zxy?") == "???321??xyz?")  # 输出 True


# Day11   30有限制的楼梯攀登   2024/11/19
def solution(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

    # 初始化 dp 数组
    dp = [0] * (n + 1)
    dp[0] = 1  # 第 0 层
    dp[1] = 1  # 第 1 层
    dp[2] = 2  # 第 2 层

    # 根据递推公式计算 dp[i]
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 3]

    return dp[n]


if __name__ == "__main__":
    # 测试用例
    print(solution(2) == 2)  # 输出 True
    print(solution(3) == 3)  # 输出 True
    print(solution(4) == 4)  # 输出 True


# Day11   31摇色子的胜利概率   2024/11/19
def solution(n, m, arrayN, arrayM):
    def calculate_probability(dice):
        """计算骰子总和的概率分布"""
        max_sum = sum(dice)  # 最大点数和
        min_sum = len(dice)  # 最小点数和
        dp = [0] * (max_sum + 1)
        dp[0] = 1  # 初始状态，和为0的概率为1

        for sides in dice:
            for s in range(max_sum, -1, -1):
                dp[s] = sum(dp[s - i] if s - i >= 0 else 0 for i in range(1, sides + 1)) / sides

        return dp[min_sum : max_sum + 1]

    # 计算小U和小S的点数概率分布
    prob_u = calculate_probability(arrayN)
    prob_s = calculate_probability(arrayM)

    # 胜率计算
    prob_u_wins = 0
    for i, p_u in enumerate(prob_u):
        for j, p_s in enumerate(prob_s):
            if i + len(arrayN) > j + len(arrayM):  # 小U的点数大于小S
                prob_u_wins += p_u * p_s

    return round(prob_u_wins, 3)

if __name__ == "__main__":
    # 测试用例
    print(solution(1, 3, [8], [2, 3, 4]) == 0.255)
    print(solution(2, 2, [3, 4], [3, 3]) == 0.5)
    print(solution(3, 1, [2, 2, 2], [4]) == 0.844)


# Day12   32字符串最短循环字串   2024/11/20
def solution(inp):
    n = len(inp)

    # 遍历所有可能的子串长度
    for l in range(1, n // 2 + 1):
        if n % l == 0:  # l 必须是 n 的因数
            # 获取可能的子串
            substring = inp[:l]
            # 检查是否由 substring 重复拼接得到
            if substring * (n // l) == inp:
                return substring

    # 无法找到，返回空字符串
    return ""


if __name__ == "__main__":
    # 测试样例
    print(solution("abcabcabcabc") == "abc")
    print(solution("aaa") == "a")
    print(solution("abababab") == "ab")
    print(solution("ab") == "")
    print(solution("abcdabcdabcdabcd") == "abcd")
    print(solution("b") == "")


# Day12   33优秀项目组初选评比   2024/11/20
def solution(m, n, a):
    # 对数组进行升序排序
    a.sort()
    length = len(a)
    result = -1

    # 枚举分数线 x
    for i in range(length):
        x = a[i]
        k1 = sum(1 for score in a if score > x)  # 大于 x 的项目组数量
        k2 = sum(1 for score in a if score <= x)  # 小于等于 x 的项目组数量

        # 检查条件
        if m <= k1 <= n and m <= k2 <= n:
            if result == -1 or x < result:
                result = x

    return result


if __name__ == "__main__":
    # 测试样例
    print(solution(2, 3, [1, 2, 3, 5, 6, 4]) == 3)
    print(solution(1, 2, [7, 8, 9, 3, 5]) == -1)
    print(solution(1, 4, [7, 8, 9, 3, 5]) == 3)


# Day12   34区间内排列的数量   2024/11/20
def solution(n, a):
    count = 0

    # 遍历所有可能的起始点
    for l in range(n):
        seen = set()  # 用来记录当前子区间的元素
        max_val = float('-inf')  # 当前子区间的最大值
        min_val = float('inf')  # 当前子区间的最小值

        # 从起点开始扩展终点
        for r in range(l, n):
            # 如果出现重复元素，停止当前子区间的探索
            if a[r] in seen:
                break

            # 添加当前元素到集合
            seen.add(a[r])
            # 更新最大值和最小值
            max_val = max(max_val, a[r])
            min_val = min(min_val, a[r])

            # 判断是否满足排列条件
            if max_val - min_val + 1 == r - l + 1 and min_val == 1:
                count += 1

    return count


if __name__ == "__main__":
    # 测试样例
    print(solution(5, [2, 1, 5, 3, 4]) == 3)  # [2,1], [5,3,4], [1,5,3,4]
    print(solution(5, [1, 2, 3, 4, 5]) == 5)  # [1], [1,2], [1,2,3], ...
    print(solution(4, [4, 3, 2, 1]) == 4)  # [4], [3,2], [2,1], [4,3,2,1]


# Day13   35套碗的取碗顺序问题二   2024/11/21
def solution(M: int) -> int:
    """
    计算卡塔兰数 C(M)，表示 M 个碗的合法取碗顺序数。
    """
    if M == 0:
        return 1

    # 初始化卡塔兰数数组
    catalan = [0] * (M + 1)
    catalan[0] = 1  # C(0) = 1

    # 通过递推公式计算
    for n in range(1, M + 1):
        catalan[n] = sum(catalan[i] * catalan[n - 1 - i] for i in range(n))

    return catalan[M]


if __name__ == "__main__":
    # 测试样例
    print(solution(2) == 2)  # 输出 2
    print(solution(3) == 5)  # 输出 5
    print(solution(4) == 14)  # 输出 14


# Day14   36小B的极差之和   2024/11/22
def solution(n: int, a: list) -> int:
    MOD = 10 ** 9 + 7  # 模数，用于结果取模

    # 构造数组 b
    b = []
    for i, count in enumerate(a):
        b.extend([i + 1] * count)  # 每个值 i+1 在 b 中出现 count 次

    m = len(b)  # 数组 b 的长度

    # 单调栈计算贡献
    def calculate_contribution(b, is_max):
        """
        使用单调栈计算所有元素作为最大值或最小值的贡献。
        :param b: 输入数组
        :param is_max: 是否计算最大值的贡献
        :return: 对应贡献的总和
        """
        stack = []  # 单调栈
        left = [-1] * m  # 每个元素左边界的索引
        right = [m] * m  # 每个元素右边界的索引

        for i in range(m):
            # 如果是最大值，栈中递减；如果是最小值，栈中递增
            while stack and ((b[stack[-1]] < b[i]) if is_max else (b[stack[-1]] > b[i])):
                right[stack.pop()] = i  # 更新右边界
            left[i] = stack[-1] if stack else -1  # 更新左边界
            stack.append(i)

        # 计算贡献
        contribution = 0
        for i in range(m):
            l = left[i] + 1  # 左边界对应的实际范围
            r = right[i] - 1  # 右边界对应的实际范围
            # 当前值的贡献：b[i] * 左边长度 * 右边长度
            contribution += b[i] * (i - l + 1) * (r - i + 1)
            contribution %= MOD  # 每步都取模，防止溢出
        return contribution

    # 分别计算最大值和最小值的贡献
    max_sum = calculate_contribution(b, True)  # 最大值的贡献
    min_sum = calculate_contribution(b, False)  # 最小值的贡献

    # 最终结果为两者的差值
    return (max_sum - min_sum + MOD) % MOD


if __name__ == '__main__':
    # 测试样例
    print(solution(2, [2, 1]) == 2)  # 测试用例1
    print(solution(3, [1, 2, 1]) == 6)  # 测试用例2
    print(solution(4, [2, 3, 1, 1]) == 26)  # 测试用例3


# Day14   37小C和小U   2024/11/22
def solution(l1, r1, l2, r2, l3, r3):
    # 定义区间
    intervals = [(l1, r1), (l2, r2), (l3, r3)]

    # 定义两个函数来检查交集和求最大交集
    def has_overlap(interval1, interval2):
        """检查两个区间是否有交集"""
        return not (interval1[1] < interval2[0] or interval2[1] < interval1[0])

    def max_overlap(interval1, interval2):
        """返回两个区间的最大交集范围"""
        if has_overlap(interval1, interval2):
            return max(interval1[0], interval2[0]), min(interval1[1], interval2[1])
        return None

    max_sum = -1  # 初始化最大和为 -1

    # 枚举两人选取的区间
    for i in range(3):  # 小C选择的区间
        for j in range(3):  # 小U选择的区间
            if i == j:  # 区间不能相同
                continue
            overlap = max_overlap(intervals[i], intervals[j])  # 计算交集
            if overlap:
                # 交集范围的最大值
                max_value = overlap[1]
                # 选择尽可能大的两个值
                max_sum = max(max_sum, 2 * max_value)

    return max_sum

if __name__ == '__main__':
    # 测试用例
    print(solution(1, 3, 2, 4, 4, 6))  # 输出：8
    print(solution(1, 2, 2, 3, 3, 4))  # 输出：6
    print(solution(10, 20, 15, 25, 30, 40))  # 输出：40


# Day14   38小C的w五元组问题   2024/11/22
def solution(n: int, a: list) -> int:
    MOD = 10 ** 9 + 7  # 模值
    from collections import defaultdict

    # 记录每个数出现的位置索引
    value_indices = defaultdict(list)
    for idx, val in enumerate(a):
        value_indices[val].append(idx + 1)

    result = 0  # 计数结果

    # 遍历所有可能的 a[i] > a[j]
    for ai in value_indices.keys():
        for aj in value_indices.keys():
            if ai <= aj:  # 确保 a[i] > a[j]
                continue

            # 分别获取对应数值的索引列表
            indices_ai = value_indices[ai]  # 值为 ai 的索引
            indices_aj = value_indices[aj]  # 值为 aj 的索引

            # 对于每一对 (i, k, l)，计算 j 和 h 的数量
            for i_idx in range(len(indices_ai) - 2):
                for k_idx in range(i_idx + 1, len(indices_ai) - 1):
                    for l_idx in range(k_idx + 1, len(indices_ai)):
                        i, k, l = indices_ai[i_idx], indices_ai[k_idx], indices_ai[l_idx]

                        # 统计满足 j 和 h 的数量
                        count_jh = 0
                        for j in indices_aj:
                            if i < j < k:  # j 必须在 i 和 k 之间
                                for h in indices_aj:
                                    if k < h < l:  # h 必须在 k 和 l 之间
                                        count_jh += 1

                        # 更新结果
                        result = (result + count_jh) % MOD

    return result


if __name__ == '__main__':
    # 测试用例
    print(solution(7, [3, 1, 3, 1, 3, 1, 3]))  # 输出：6
    print(solution(6, [2, 1, 2, 1, 2, 1]))  # 输出：1
    print(solution(5, [5, 3, 5, 3, 5]))  # 输出：1


# Day14   39小C的回文博弈   2024/11/22
def solution(s: str) -> str:
    from collections import Counter

    # 统计每个字符出现的次数
    freq = Counter(s)
    odd_count = sum(1 for count in freq.values() if count % 2 != 0)

    # 根据奇数次数的个数判断胜负
    if odd_count <= 1:
        return 'C'  # 小C直接获胜
    else:
        return 'C' if (odd_count - 1) % 2 == 0 else 'U'

# 测试用例
if __name__ == '__main__':
    print(solution("aab"))  # 输出：'C'
    print(solution("abc"))  # 输出：'C'
    print(solution("abcd"))  # 输出：'U'


# Day15   40小C的帖子吸引力最大化   2024/11/23
def solution(n: int, a: list, b: list) -> int:
    offset = sum(max(a[i] - b[i], b[i] - a[i]) for i in range(n))  # 最大可能的差值范围
    dp = [-float('inf')] * (2 * offset + 1)  # 初始化 DP 数组
    dp[offset] = 0  # 初始状态，差值为 0

    for i in range(n):
        diff = a[i] - b[i]  # 当前帖子的点赞数和点踩数的差
        new_dp = dp[:]
        for j in range(-offset, offset + 1):
            if dp[j + offset] != -float('inf'):
                # 更新选择当前帖子的状态
                new_dp[j + diff + offset] = max(new_dp[j + diff + offset], dp[j + offset] + a[i] + b[i])
                # 更新不选择当前帖子的状态
                new_dp[j + offset] = max(new_dp[j + offset], dp[j + offset])
        dp = new_dp

    # 返回最大绝对差
    max_abs_diff = 0
    for j in range(-offset, offset + 1):
        if dp[j + offset] != -float('inf'):
            max_abs_diff = max(max_abs_diff, abs(j))

    return max_abs_diff


# 测试样例
print(solution(4, [4, 2, 1, 1], [2, 1, 4, 4]))  # 输出：6
print(solution(3, [10, 20, 30], [15, 25, 5]))  # 输出：25
print(solution(5, [1, 5, 3, 7, 9], [2, 6, 4, 8, 10]))  # 输出：5


# Day15   41小C的逆序对挑战   2024/11/23
def solution(n: int, x: int, y: int, a: list) -> int:
    # 初始化最小操作次数为一个大值
    min_operations = float('inf')

    for i in range(n):
        for j in range(i + 1, n):
            if a[i] > a[j]:  # 已经存在逆序对
                return 0

            # 计算将 a[i] > a[j] 所需的操作次数
            if a[i] <= a[j]:
                diff = a[j] - a[i] + 1
                operations = min(
                    (diff + x - 1) // x,  # 通过加法操作 a[i] 增大到 a[j] + 1
                    (diff + y - 1) // y  # 通过减法操作 a[j] 减小到 a[i] - 1
                )
                min_operations = min(min_operations, operations)

    return min_operations


if __name__ == '__main__':
    print(solution(3, 1, 2, [1, 3, 5]) == 2)
    print(solution(4, 5, 7, [4, 6, 10, 9]) == 0)
    print(solution(5, 3, 2, [7, 7, 7, 7, 7]) == 1)


# Day16   42小E的按位与挑战  2024/11/24
def solution(n: int, a: list) -> int:
    """
    找到能够使得按位与结果可被 2^m 整除，并使 m 最大的子集对应的 m 值。

    参数：
    - n: 数组的长度
    - a: 数组列表

    返回：
    - 能够使得 m 最大化的值
    """
    max_m = 0

    # 遍历可能的 m 值（从大到小找，以优化性能）
    for m in range(31, -1, -1):
        divisor = 1 << m  # 2^m
        subset = [x for x in a if x % divisor == 0]

        if subset:
            # 检查这个子集的按位与是否非 0
            and_result = subset[0]
            for num in subset[1:]:
                and_result &= num
            if and_result % divisor == 0:
                max_m = m
                break

    return max_m


# 测试用例
if __name__ == "__main__":
    print(solution(5, [1, 2, 3, 20, 28]) == 2)  # 示例1
    print(solution(4, [16, 8, 4, 2]) == 4)  # 示例2
    print(solution(6, [7, 14, 28, 56, 112, 224]) == 5)  # 示例3
    print(solution(3, [1, 2, 4]) == 0)  # 边界情况
    print(solution(2, [1024, 2048]) == 10)  # 自定义示例


# Day16   43小E的糖果工厂挑战  2024/11/24
def solution(n: int, a: int, b: int, candies: list[int]) -> int:
    """
    计算工厂完成订单所需的最少天数。

    参数：
    - n: 糖果种类数量
    - a: 需要的糖果包数
    - b: 每包糖果的最小数量
    - candies: 每种糖果每天的生产数量列表

    返回：
    - 至少需要的天数
    """
    # 计算每种糖果每天能生产的满足要求的包数
    daily_bags = [c // b for c in candies]

    # 初始化二分查找的范围
    left, right = 1, a * b  # 最少1天，最多所有糖果每天生产满足所有包

    while left < right:
        mid = (left + right) // 2

        # 检查mid天内能生产的总包数是否满足要求
        total_bags = sum((c * mid) // b for c in candies)
        if total_bags >= a:
            right = mid  # 如果能满足需求，尝试更少的天数
        else:
            left = mid + 1  # 否则增加天数

    return left


# 测试用例
if __name__ == "__main__":
    # 示例测试
    print(solution(3, 10, 20, [7, 9, 6]) == 10)  # 示例1
    print(solution(4, 5, 15, [3, 10, 8, 4]) == 4)  # 示例2
    print(solution(2, 100, 5, [1, 10]) == 46)  # 示例3

    # 边界测试
    print(solution(1, 1, 1, [1]) == 1)  # 只有一种糖果且需求为1包1个
    print(solution(2, 100, 10, [10, 20]) == 5)  # 多种糖果混合计算
    print(solution(5, 50, 25, [100, 200, 300, 400, 500]) == 1)  # 大量糖果需求少天数


# Day16   44小C的点菜问题  2024/11/24
from collections import Counter

def solution(m: int, w: list[int]) -> int:
    """
    计算小C最多可以点多少道价格相同的菜。

    参数：
    - m: 菜品的价格上限
    - w: 菜品的价格列表

    返回：
    - 小C最多可以点的菜品数量
    """
    # 过滤掉超过 m 的菜品
    valid_prices = [price for price in w if price <= m]
    # 统计每个价格的出现次数
    count = Counter(valid_prices)
    # 返回出现次数最多的价格对应的数量
    return max(count.values(), default=0)

# 测试用例
if __name__ == "__main__":
    # 示例测试
    print(solution(6, [2, 3, 3, 6, 6, 6, 9, 9, 23]))  # 输出: 3
    print(solution(4, [1, 2, 4, 4, 4]))               # 输出: 3
    print(solution(5, [5, 5, 5, 5, 6, 7, 8]))         # 输出: 4

    # 边界测试
    print(solution(1, [2, 3, 4]))                     # 输出: 0
    print(solution(10, [1, 1, 1, 2, 2, 3, 3, 3]))     # 输出: 3
    print(solution(5, []))                            # 输出: 0
    print(solution(7, [7, 7, 7, 7, 7]))               # 输出: 5


# Day17   45小C的好数  2024/11/25
def solution(n: int):
    def is_good(num):
        digits = set(str(num))
        return len(digits) <= 2

    count = 0
    for i in range(1, n + 1):
        if is_good(i):
            count += 1

    return count

# 测试用例
print(solution(110))  # 输出: 102
print(solution(1000)) # 输出: 352
print(solution(1))    # 输出: 1


# Day17   45小C的数字倍数问题  2024/11/25
import math


# 计算一个数 x 在 [1, r] 区间内的倍数个数
def count_multiples(x, r):
    return r // x


# 计算最小公倍数 lcm(a, b)
def lcm(a, b):
    return (a * b) // math.gcd(a, b)


# 计算在区间 [l, r] 内，满足是 a, b, c 的倍数的数的个数
def solution(a, b, c, l, r):
    # 计算区间 [1, r] 内的倍数个数
    count_r = (count_multiples(a, r) + count_multiples(b, r) + count_multiples(c, r)
               - count_multiples(lcm(a, b), r) - count_multiples(lcm(b, c), r) - count_multiples(lcm(a, c), r)
               + count_multiples(lcm(a, lcm(b, c)), r))

    # 计算区间 [1, l-1] 内的倍数个数
    count_l_minus_1 = (count_multiples(a, l - 1) + count_multiples(b, l - 1) + count_multiples(c, l - 1)
                       - count_multiples(lcm(a, b), l - 1) - count_multiples(lcm(b, c), l - 1) - count_multiples(
                lcm(a, c), l - 1)
                       + count_multiples(lcm(a, lcm(b, c)), l - 1))

    # 最终结果为 count_r 减去 count_l_minus_1
    return count_r - count_l_minus_1


# 测试用例
print(solution(2, 3, 4, 1, 10))  # 输出: 7
print(solution(5, 7, 11, 15, 100))  # 输出: 34
print(solution(1, 1, 1, 1, 1000))  # 输出: 1000


# Day18   46小C的类二进制拼图  2024/11/26
def solution(n: str) -> int:
    """
    计算将正整数 n 表示为类二进制数字之和所需的最少个数。
    输入:
        n: str - 表示正整数的字符串
    输出:
        int - 最少需要的类二进制数字个数
    """
    # 直接返回 n 的最高位数字
    return max(map(int, n))

# 测试用例
print(solution("10101"))       # 输出: 1
print(solution("212"))         # 输出: 2
print(solution("1000000"))     # 输出: 1
print(solution("123456789"))   # 输出: 9
print(solution("9876543210"))  # 输出: 9


# Day19   47小E的倍数关系子集问题  2024/11/27
def solution(n: int, a: list[int]) -> int:
    """
    计算满足条件的子集数量，结果对 10^9 + 7 取模。

    输入:
        n: int - 数组长度
        a: list[int] - 元素数组
    输出:
        int - 满足条件的子集数量
    """
    MOD = 10**9 + 7
    a.sort()  # 对数组进行排序
    dp = [0] * n  # dp[i] 表示以 a[i] 为最大值的合法子集数量

    for i in range(n):
        dp[i] = 1  # 初始化，每个元素单独可以构成一个子集
        for j in range(i):
            if a[i] % a[j] == 0:  # 满足倍数关系
                dp[i] += dp[j]
                dp[i] %= MOD

    # 总的合法子集数量减去单元素子集数量
    total = sum(dp) % MOD
    result = (total - n) % MOD  # 减去单元素子集
    return result if result >= 0 else (result + MOD)

# 测试用例
print(solution(5, [1, 2, 3, 4, 5]))  # 输出: 6
print(solution(6, [2, 4, 8, 16, 32, 64]))  # 输出: 57
print(solution(4, [3, 6, 9, 12]))  # 输出: 5


# Day19   48小G的平衡串转换  2024/11/27
def solution(s: str) -> int:
    """
    将字符串转化为平衡串所需的最少操作次数。

    参数:
        s (str): 输入字符串

    返回:
        int: 最少操作次数
    """
    n = len(s)
    count_a = s.count('a')
    count_b = s.count('b')
    count_c = s.count('c')

    # 目标数量
    target_a = n // 2
    target_bc = n // 2

    # 计算需要的调整
    change_a = max(0, count_a - target_a)
    change_bc = max(0, (count_b + count_c) - target_bc)

    # 返回调整的总次数
    return max(change_a, change_bc)


# 测试用例
print(solution("abca"))  # 输出: 0
print(solution("abbc"))  # 输出: 1
print(solution("ccbcca"))  # 输出: 2


# Day19   49小F的相似密码问题  2024/11/27
def solution(n: int, k: int, s: str, t: str) -> bool:
    """
    判断通过最多 k 次操作，是否可以将 s 转换为 t。

    输入:
        n: int - 密码长度
        k: int - 最多操作次数
        s: str - 第一个密码
        t: str - 第二个密码

    输出:
        bool - 是否可以通过最多 k 次操作将 s 转换为 t
    """
    for i in range(n):
        # 计算字符 s[i] 到 t[i] 的最小操作次数
        distance = (ord(t[i]) - ord(s[i])) % 26
        if distance > k:
            return False
    return True


# 测试用例
print(solution(4, 3, "abcd", "cdef"))  # 输出: True
print(solution(4, 1, "abcd", "cdef"))  # 输出: False
print(solution(5, 2, "abcde", "cdefg"))  # 输出: True


# Day20   50小M的37进制数字相乘问题  2024/11/28
def solution(a: str, b: str) -> str:
    """
    计算两个 37 进制数的乘积，并返回结果的 37 进制表示。

    参数:
        a (str): 第一个 37 进制数
        b (str): 第二个 37 进制数

    返回:
        str: 乘积的 37 进制表示
    """
    # 37 进制字符集
    chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
    char_to_value = {ch: i for i, ch in enumerate(chars)}
    value_to_char = {i: ch for i, ch in enumerate(chars)}

    # 37 进制转十进制
    def base37_to_decimal(s: str) -> int:
        result = 0
        for ch in s:
            result = result * 37 + char_to_value[ch]
        return result

    # 十进制转 37 进制
    def decimal_to_base37(num: int) -> str:
        if num == 0:
            return "0"
        result = []
        while num > 0:
            result.append(value_to_char[num % 37])
            num //= 37
        return ''.join(reversed(result))

    # 转换 a 和 b 为十进制
    decimal_a = base37_to_decimal(a)
    decimal_b = base37_to_decimal(b)

    # 计算乘积
    product = decimal_a * decimal_b

    # 转换结果为 37 进制
    return decimal_to_base37(product)


# 测试用例
print(solution("Z", "X"))  # 输出: 'V8'
print(solution("A", "B"))  # 输出: '2$'


# Day21   51小Q和小X的游戏  2024/11/29
from math import gcd
from functools import lru_cache

def solution(n: int, a: list[int]) -> str:
    # 构建合法移动图
    smaller_left = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i - 1, -1, -1):
            if a[j] < a[i]:
                smaller_left[i].append(j)

    # 使用缓存避免重复计算
    @lru_cache(None)
    def can_win(pos: int, turn: int) -> bool:
        """
        判断从位置 pos 开始，当前轮到 turn 的玩家是否能获胜
        turn: 0 表示小Q, 1 表示小X
        """
        for next_pos in smaller_left[pos]:
            if not can_win(next_pos, 1 - turn):  # 对方输了，我就赢了
                return True
        return False  # 如果所有的子路径都无法让我赢，当前必败

    # 计算小Q必胜的起点数
    win_count = 0
    for start in range(n):
        if can_win(start, 0):  # 小Q从 start 出发，先行动
            win_count += 1

    # 化简分数
    total = n
    g = gcd(win_count, total)
    return f"{win_count // g}/{total // g}"

# 测试用例
print(solution(5, [3, 1, 5, 4, 3]))  # 输出: '3/5'
print(solution(6, [6, 2, 9, 7, 4, 3]))  # 输出: '2/3'
print(solution(4, [8, 5, 6, 3]))  # 输出: '1/4'


# Day21   52小R的三倍数分解挑战  2024/11/29
def solution(n: int) -> int:
    MOD = 10 ** 9 + 7

    # 如果 n 不是 3 的倍数，或者太小无法分解，直接返回 0
    if n % 3 != 0 or n < 9:
        return 0

    # 转化为 t = n // 3
    t = n // 3

    # 计算组合数 C(t - 1, 2) = (t - 1) * (t - 2) // 2
    if t < 3:
        return 0
    result = (t - 1) * (t - 2) // 2
    return result % MOD


# 测试用例
print(solution(9))  # 输出: 1
print(solution(12))  # 输出: 3
print(solution(15))  # 输出: 6
print(solution(18))  # 输出: 10
print(solution(6))  # 输出: 0








